#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {

public:
    void dfs(vector<vector<int>>& ans, vector<int>& nums, vector<bool>& st, vector<int>& an)
    {
        if (an.size() == nums.size())
        {

            ans.push_back(an);


            return;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            if (st[i] == false)
            {
                if (i > 0 && nums[i] == nums[i - 1] && st[i - 1] == false)
                    continue;
                an.push_back(nums[i]);
                st[i] = true;
                dfs(ans, nums, st, an);
                st[i] = false;
                an.pop_back();


            }

        }
        return;


    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> an;
        vector<bool>st(nums.size());
        sort(nums.begin(), nums.end());
        dfs(ans, nums, st, an);

        return ans;
    }
};